package com.ming.learn.from.carl.binary.tree;


import com.ming.commons.utils.TreeNode;

import java.time.temporal.Temporal;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/*
257. 二叉树的所有路径
 */
public class Of20210310LeetCode257 {
    /*
    给定一个二叉树，返回所有从根节点到叶子节点的路径。
    说明: 叶子节点是指没有子节点的节点。
     */
    public static void main(String[] args) {
        System.out.println(binaryTreePaths2(new TreeNode(1, new TreeNode(2, null, new TreeNode(5)), new TreeNode(3))));
    }

    /*
    递归
     */
    private static void traversal(TreeNode cur, String path, List<String> result) {
        path += cur.val + ""; // 中
        if (cur.left == null && cur.right == null) {
            result.add(path);
            return;
        }
        if (cur.left != null) traversal(cur.left, path + "->", result); // 左
        if (cur.right != null) traversal(cur.right, path + "->", result); // 右
    }

    private static List<String> binaryTreePaths(TreeNode root) {
        if (root == null) return null;
        ArrayList<String> result = new ArrayList<>();
        String path = "";
        traversal(root, path, result);
        return result;
    }

    /*
    迭代法
     */
    private static List<String> binaryTreePaths2(TreeNode root) {
        Stack<TreeNode> treeNodeStack = new Stack<>();// 保存树的遍历节点
        Stack<String> stringStack = new Stack<>();// 保存遍历路径的节点
        // 只用一个栈 也可以Stack<Object> stack = new Stack<>();
        if (root == null) return null;
        ArrayList<String> result = new ArrayList<>();// 保存最终路径集合
        treeNodeStack.push(root);
        stringStack.push(root.val + "");
        while (!treeNodeStack.isEmpty()) {
            TreeNode node = treeNodeStack.pop(); // 取出节点 中
            String path = stringStack.pop();    // 取出该节点对应的路径
            if (node.left == null && node.right == null) { // 遇到叶子节点
                result.add(path);
            }
            if (node.right != null) { // 右
                treeNodeStack.push(node.right);
                stringStack.push(path + "->" + node.right.val + "");
            }
            if (node.left != null) { // 左
                treeNodeStack.push(node.left);
                stringStack.push(path + "->" + node.left.val + "");
            }
        }
        return result;
    }
}
